ass Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right)
        {
            int mid = left+(right-left)/2;
            int tmp=nums[mid];
            if(target>tmp) left=mid+1;
            else if(target<tmp) right=mid-1;
            else return left+(right-left)/2;
        }
        return -1;
    }
};

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0)
        return {-1,-1};

        int left=0,right=nums.size()-1;
        int begin=0,end=0;
        //1. 二分左端点
        while(left<right)
        {
            int mid=left+(right-left)/2;//注意这里要判断两端点左边的
            if(nums[mid]<target) left=mid+1;//注意这里是<
            else right=mid;
        }
        //判断是否有结果
        if(nums[left]!=target) return {-1,-1};
        begin=left;
        left=0,right=nums.size()-1;
        //2. 二分右断点
        while(left<right)
        {
            int mid=left+(right-left+1)/2;//注意这里要判断两端点右边的
            if(nums[mid]<=target) left=mid;//注意这里是<=
            else right=mid-1;
        }
        if(nums[left]!=target) return {-1,-1};
        end=left;
        return {begin,right};
    }
};

class Solution {
public:
    int mySqrt(int x) {
        if(x<1) return 0;
        long long left=0,right=x;
        while(left<right)
        {
            long long mid = left+(right-left+1)/2;
            if(mid*mid <= x) left=mid;
            else right=mid-1;
        }
        return right;
    }
};<Paste>

class Solution {
  public:
    int searchInsert(vector<int>& nums, int target) {
              int left=0,right=nums.size()-1;
                      while(left<right)
                      {
                                    int mid = left+(right-left)/2;
                                                if(nums[mid]<target) left=mid+1;
                                                            else right=mid;
                                                                    
                      }
                              if(nums[left]<target) return left+1;
                                      return left;
                                          
    }

};

class Solution {
  public:
    int peakIndexInMountainArray(vector<int>& arr) {
              int left=0,right=arr.size()-1;
                      while(left<right)
                      {
                                    int mid = left+(right-left+1)/2;
                                                if(arr[mid]>arr[mid-1]) left=mid;
                                                            else right=mid-1;
                                                                    
                      } 
                              return left;
                                  
    }

};

class Solution {
  public:
    int findPeakElement(vector<int>& nums) {
              int left=0, right=nums.size()-1;
                      while(left<right)
                      {
                                    int mid = left+(right-left)/2;
                                                if(nums[mid]<nums[mid+1]) left=mid+1;
                                                            else right=mid;
                                                                    
                      }
                              return left;
                                  
    }

};

class Solution {
  public:
    int findMin(vector<int>& nums) {
              // 4 5 6 7 0 1 2
              //         int left=0,right=nums.size()-1;
              //                 int x=nums[right];
              //                         while(left<right)
              //                                 {
              //                                             int mid=left+(right-left)/2;
              //                                                         if(nums[mid]>x) left=mid+1;
              //                                                                     else right=mid; 
              //                                                                             }
              //                                                                                     return nums[left];
              //                                                                                         }
              //                                                                                         };
              //                                 }
    }
}

class Solution {
  public:
    int missingNumber(vector<int>& nums) {
              int left=0,right=nums.size()-1;
                      while(left<right)
                      {
                                    int mid = left+(right-left)/2;
                                                if(nums[mid]==mid) left=mid+1;
                                                            else right=mid;
                                                                    
                      }
                              //处理细节问题，数组就是升序的时候
                              //        if(left==nums[left]) return left+1;
                              //                else return left;
                              //                    
    }

};


